package com.yaoli.ajob;

/**
 * 动态规划
 *
 * 用一个数组记录 前一个前一个的最大值
 *
 * 因为是不能连续的数组，所以比较 i - 2 和 i - 3 的最大值
 *
 * Created by will on 2017/4/22.
 */
public class _198_HouseRobber {
    public static void main(String[] args) {
        _198_HouseRobber climbingStairs = new _198_HouseRobber();

        int nums [] = {2,1,1,2};
        System.out.println(climbingStairs.rob(nums));


    }
    public int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }else if(nums.length == 1){
            return nums[0];
        }else if(nums.length == 2){
            return Math.max(nums[0],nums[1]);
        }

        int dp [] = new int[nums.length+1];
        dp[0] = 0;
        dp[1] = nums[0];
        dp[2] = nums[1];

        for (int i = 3; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 2],dp[i-3])+nums[i - 1];
        }

        return Math.max(dp[dp.length - 1],dp[dp.length - 2]);
    }
}
